<?php 
/** 
 * 数字在排序数组中出现的次数
 * 用二分法找出该数字第一次出现的位置
 * 用二分法找出该数字最后一次出现的位置
 */

function GetNumberOfK($data, $k)
{
	if (empty($data)) {
		return -1;
	}

	$number = 0;
	$length = count($data); 
   	$first = GetNumberOfFirst($data, $length, $k, 0, $length - 1);
   	$last = GetNumberOfLast($data, $length, $k, 0, $length - 1);

   	if ($first > -1 && $last > 1) {
   		$number = $last - $first + 1;
   	}
   	return $number;

}

/** 
 * 找出K第一次出现的索引值
 * @param [type] $data   [description]
 * @param [type] $length [description]
 * @param [type] $k      [description]
 * @param [type] $start  [description]
 * @param [type] $end    [description]
 */
function GetNumberOfFirst($data, $length, $k, $start, $end)
{
    if ($start > $end) {
    	return -1;
    }
    $mid = intval(($start + $end) / 2);
    $midData = $data[$mid];
    if ($midData == $k) {
    	if (($mid > 0 && $data[$mid - 1] != $k) || $mid == 0) {
    		return $mid;
    	} else {
    		$end = $mid - 1;
    	}
    } elseif ($k < $midData) {
    	$end = $mid - 1;
    } else {
    	$start = $mid + 1;
    }
    return GetNumberOfFirst($data, $length, $k, $start, $end);
}


/** 
 * 找出K最后一次出现的索引值
 * @param [type] $data   [description]
 * @param [type] $length [description]
 * @param [type] $k      [description]
 * @param [type] $start  [description]
 * @param [type] $end    [description]
 */
function GetNumberOfLast($data, $length, $k, $start, $end)
{
    if ($start > $end) {
    	return -1;
    }
    $mid = intval(($start + $end) / 2);
    $midData = $data[$mid];
    if ($midData == $k) {
    	if (($mid < ($length -1) && $data[$mid + 1] != $k) || $mid == ($length - 1)) {
    		return $mid;
    	} else {
    		$start = $mid + 1;
    	}
    } elseif ($k < $midData) {
    	$end = $mid - 1;
    } else {
    	$start = $mid + 1;
    }
    return GetNumberOfLast($data, $length, $k, $start, $end);
}


$data = [1,2,3,5,5,5,5,5,6,9,8,7];
var_dump(GetNumberOfK($data, 3));